package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/permutation-sequence/description/
 * The set [1,2,3,…,n] contains a total of n! unique permutations.
 * By listing and labeling all of the permutations in order,
 * We get the following sequence (ie, for n = 3):
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * Given n and k, return the kth permutation sequence.
 */
public class LC_060_PermutationSequence_Perm {
    public static void main(String[] args) {
        for (int i = 1; i < 6; i++) {
            System.out.println(Solution.getPermutation(5, i));
        }
    }

    static class Solution {
        static String getPermutation(int n, int k) {
            k--;

            List<Integer> numList = new ArrayList<>();
            for (int i = 1; i <= n; i++)
                numList.add(i);

            int factorial = 1;
            for (int i = 2; i < n; i++)
                factorial *= i;

            StringBuilder res = new StringBuilder();
            int times = n - 1;

            while (times >= 0) {
                int indexInList = k / factorial;
                res.append(numList.get(indexInList));
                numList.remove(indexInList);

                k = k % factorial;
                if (times != 0)
                    factorial = factorial / times;

                times--;
            }

            return res.toString();
        }
    }
}
